package com.dexing.od1;


import java.util.Scanner;

/**
 * <blockquote> 
 *  小明每周上班都会拿到自己的工作清单，工作清单内包含n项工作，每项工作都有对应的耗时时间（单位h）和报酬, 
 *  工作的总报酬为所有已完成工作的报酬之和，那么请你帮小明安排一下工作，保证小明在指定的工作时间内工作收入最大化。
 *  输入描述
 *  输入的第一行为两个正整数T，n。 T代表工作时长（单位h，0<T<1000000），n代表工作数量（1<n≤3000）。
 *  接下来是n行，每行包含两个整数t，w。 t代表该工作消耗的时长（单位h，t>0）,w代表该项工作的报酬。
 *  输出描述
 *  输出小明制定工作时长内工作可获得的最大报酬。
 *  示例一 输入
 *  40 3
 *  20 10
 *  20 20
 *  20 5
 *  输出
 *  30 
 * </blockquote>
 */
public class D2087Salary {
    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        int n = in.nextInt();
        in.nextLine();
        int[][] tasks = new int[n][2];
        for (int i = 0; i < n; i++) {
            tasks[i][0] = in.nextInt();
            tasks[i][1] = in.nextInt();
            in.nextLine();
        }

        //从耗时最小的任务开始
        int min_time = Integer.MAX_VALUE;
        for (int[] task : tasks) {
            min_time = Math.min(min_time, task[0]);
        }

        //dp
        int[][] dp = new int[n + 1][T + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = min_time; j <= T; j++) {
                int last = dp[i - 1][j];
                int current = tasks[i - 1][0] > j ? 0 : tasks[i - 1][1] + dp[i - 1][j - tasks[i - 1][0]];
                dp[i][j] = Math.max(last, current);
            }
        }
        System.out.print(dp[n][T]);

    }
}
